

//合并k个有序链表非递归(优先级队列)
class Solution {
public:
    struct cmp{
        bool operator()(ListNode*& l1,ListNode*& l2)
        {
            return l1->val > l2->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,cmp> heap;   
        for(auto l : lists)
            if(l)   heap.push(l);

        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;
        while(!heap.empty())
        {
            auto top = heap.top();
            heap.pop();
            prev->next = top;
            prev = prev->next;
            if(top->next)
                heap.push(top->next);    
        }

        prev = newhead->next;
        delete newhead;
        return prev;
    }
};


//合并k个有序链表(递归归并)
class Solution {
public:

    ListNode* _merge(vector<ListNode*> lists,int l,int r)
    {
        if(l > r)   return nullptr;
        if(l == r)  return lists[l];

        int mid = l + (r - l) / 2;
        ListNode* left = _merge(lists,l,mid);
        ListNode* right = _merge(lists,mid + 1,r);

        return mergeTwoList(left,right);
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* ret = _merge(lists,0,lists.size()-1);
        return ret;
    }
    ListNode* mergeTwoList(ListNode* l1,ListNode* l2)
    {
        if(l1 == nullptr)   return l2;
        if(l2 == nullptr)   return l1;

        ListNode* cur1 = l1,*cur2 = l2;
        ListNode newhead;
        newhead.next = nullptr;
        ListNode* prev = &newhead;
        while(cur1 && cur2)
        {
            if(cur1->val < cur2->val)
            {
                prev = prev->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                prev = prev->next = cur2;
                cur2 = cur2->next;
            }
        }
        if(cur1)
            prev->next = cur1;
        if(cur2)
            prev->next = cur2;

        return newhead.next;
    }
};
